#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int DataType;
typedef struct Queue
{
	DataType data;
	struct Queue* next;
}Queue;

typedef struct Q
{
	Queue* head;
	Queue* tail;
	int size;
}Q;

typedef struct {
	Q q1;
	Q q2;
} MyStack;

void Init(Q* qq);
void Destroy(Q* qq);
void QueuePush(Q* qq, DataType x);
void QueuePop(Q* qq);
DataType GetQueueFrontNum(Q* qq);
DataType GetQueueBackNum(Q* qq);
bool Empty(Q* qq);
int Size(Q* qq);

void Init(Q* qq)
{
	assert(qq);
	qq->head = NULL;
	qq->tail = NULL;
	qq->size = 0;
}

void QueuePush(Q* qq, DataType x)
{
	assert(qq);

	Queue* temp = (Queue*)malloc(sizeof(Queue));
	if (temp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	temp->data = x;
	temp->next = NULL;

	if (qq->tail == NULL)
		qq->head = qq->tail = temp;
	else
	{
		qq->tail->next = temp;
		qq->tail = temp;
	}

	qq->size++;
}

void QueuePop(Q* qq)
{
	assert(qq);
	assert(!Empty(qq));

	if (qq->head == qq->tail)
	{
		free(qq->head);
		qq->head = qq->tail = NULL;
	}
	else
	{
		Queue* next = qq->head->next;
		free(qq->head);
		qq->head = next;
	}

	qq->size--;
}

DataType GetQueueFrontNum(Q* qq)
{
	assert(qq);
	assert(!Empty(qq));

	return qq->head->data;
}

DataType GetQueueBackNum(Q* qq)
{
	assert(qq);
	assert(!Empty(qq));

	return qq->tail->data;
}

bool Empty(Q* qq)
{
	assert(qq);

	return qq->size == 0;
}

void Destroy(Q* qq)
{
	assert(qq);

	Queue* cur = qq->head;
	while (cur)
	{
		Queue* next = cur->next;
		free(cur);
		cur = next;
	}
	qq->head = qq->tail = NULL;
	qq->size = 0;
}

int Size(Q* qq)
{
	assert(qq);

	return qq->size;
}

MyStack* myStackCreate()
{

	MyStack* st = (MyStack*)malloc(sizeof(MyStack));
	Init(&st->q1);
	Init(&st->q2);

	return st;
}

void myStackPush(MyStack* obj, int x)
{
	if (!Empty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}

int myStackPop(MyStack* obj)
{
	Q* empty = &obj->q1;
	Q* obempty = &obj->q2;

	if (!Empty(&obj->q1))
	{
		empty = &obj->q2;
		obempty = &obj->q1;
	}

	int sz = Size(obempty) - 1;
	for (int i = 0; i < sz ; i++)
	{
		QueuePush(empty, GetQueueFrontNum(obempty));
		QueuePop(obempty);
	}

	int num = GetQueueFrontNum(obempty);
	QueuePop(obempty);

	return num;
}

int myStackTop(MyStack* obj)
{
	if (!Empty(&obj->q1))
	{
		return GetQueueBackNum(&obj->q1);
	}
	else
	{
		return GetQueueBackNum(&obj->q2);
	}
}

bool myStackEmpty(MyStack* obj)
{
	return (&obj->q1)->size == 0 && (&obj->q2)->size == 0;
}

void myStackFree(MyStack* obj)
{
	Destroy(&obj->q1);
	Destroy(&obj->q2);
	free(obj);
}

int main()
{
	MyStack* my_stack = myStackCreate();

	myStackPush(my_stack, 1);
	myStackPush(my_stack, 2);
	myStackPush(my_stack, 3);

	int a = myStackPop(my_stack);
	int b = myStackPop(my_stack);
	int c = myStackPop(my_stack);
	printf("%d %d %d\n", a, b, c);

	int ret = myStackEmpty(my_stack);
	printf("%d", ret);

	return 0;
}


/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/